<?php
/**
 * 不相交集类
 * 一组不相交的集合
 */
class DisjointSets
{
    /**
     * @var int[] $list 所有的元素的上级节点的索引值
     */
    public $list=[];
    /**
     * 创建不相交集类
     * @param int $size 元素数量
     */
    public function __construct($size)
    {
        $this->list=array_fill(0,$size,-1);
    }
    /**
     * 返回元素所在的集合
     * @param int $index
     */
    public function find($index)
    {
        do{
            $current=$index;
            $index=$this->list[$index];
        }
        while($index!==-1);
        return $current;
    }
    /**
     * 设置两个元素之间具有等价关系
     * 等同于合并两个不相交的集合
     * @param int $index1
     * @param int $index2
     */
    public function union($index1,$index2)
    {
        $root1=$this->find($index1);
        $root2=$this->find($index2);
        $this->list[$root2]=$root1;
    }
    public function output()
    {
        return $this->list;
    }
}




